(1) Field of the Invention
The Fast Fourier Transform (FFT) algorithm is a well known and widely used digital signal processing technique. It produces a set of N output numbers based on an arithmetic manipulation of N input numbers. This disclosure describes a digital processor for computing the FFT algorithm.
(2) Description of the Prior Art
Many FFT processors have been invented based on the different requirements of the applications for which they were intended. They share in common the use of arithmetic units for performing the necessary calculations, memory locations for holding data, and switches for directing data in the proper manner. FFT processors can be expensive, particularly when very high speed operation is desired, the number of inputs N is large, or the word length of the inputs is large. Consequently, neither the arithmetic units nor the memory locations should be wasted or used inefficiently.
Although many FFT processors based on a single arithmetic unit have been described, they are inherently unsuitable for high speed operation. A pipelined FFT processor overcomes this limitation. It employs several arithmetic units in a cascaded configuration. Many processors of this type have been implemented. One such system, as described in the textbook "Theory and Applications of Digital Signal Processing" by L. Rabiner and B. Gold, pages 604 to 606, allows for 50 percent efficiency of the arithmetic units, and requires 2(N-1)-(N/2) memory locations. Several other systems requiring only N-1 memory locations have also been described, but the arithmetic unit efficiency is still limited to only 50 percent.
One technique for achieving 100 percent arithmetic unit efficiency is to apply two additional buffers of N memory locations each and appropriate switching means to the input of the processor. In this way, a second set of N samples to be transformed can be placed into one memory while a prior set of N samples is being input to the processor from the other. However, this double buffering scheme cannot be used by some processors, nor is it efficient in its use of the memory locations.
Another system processes two channels of N samples each to achieve high arithmetic unit efficiency. Like many other systems, however, its use of the arithmetic units is only 50 percent efficient when processing a single channel of data.
The organization of the arithmetic, storage and switching means of prior art FFT processors imposes a number of restrictions on their use in applications where continuous processing in a highly efficient manner is desired. Many additional distinctions as to the utility of the prior art for use in entirely different applications can also be noted.